package com.snopy.leetcode.index1001_2000.index1101_1200;

/**
 * @author snopy
 * @version 1.0.0
 * @classname Question1137
 * @description 第 N 个泰波那契数
 * 泰波那契序列Tn定义如下：
 *
 * T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0的条件下 Tn+3 = Tn + Tn+1 + Tn+2
 *
 * 给你整数n，请返回第 n 个泰波那契数Tn 的值。
 *
 * 示例 1：
 *
 * 输入：n = 4
 * 输出：4
 * 解释：
 * T_3 = 0 + 1 + 1 = 2
 * T_4 = 1 + 1 + 2 = 4
 * 示例 2：
 *
 * 输入：n = 25
 * 输出：1389537
 * @email 77912204@qq.com
 * @date 2022/05/14 12:17
 */
public class Question1137 {
    public static void main(String[] args) {
        int tribonacci = new Question1137().tribonacci(5);
        System.out.println(tribonacci);
    }
    public int tribonacci(int n) {
        if (n<2){
            return n;
        }
        if (n == 2){
            return 1;
        }
        int p=0,q=1,k=1;
        for (int i = 3; i <=n ; i++) {
            int t = p+q+k;
            p = q;
            q = k;
            k = t;
        }
        return k;
    }
}
